﻿#include <iostream>
#include <vector>
#include <list>
#include <time.h>
#include <unordered_map>
#include <string>
#include <pthread.h>
#define MAXVEX 500000
#define TOTALTHREAD 4
#define MIN3(a,b,c) ((a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c)))

using namespace std;
#pragma comment(lib, "pthreadVC2.lib")

typedef string VertexType;      //顶点信息类型
typedef struct EdgeType
{
	int stringindex;           //抽取的字符串序号
	int startindex;           //在字符串stringindex中以startindex开始的子串
}EdgeType;

typedef struct EdgeNode         //边表结点
{
	int headvex;         //弧终点的顶点表下标
	int tailvex;        //弧起点的顶点表下标
	vector<EdgeType> info;        //(i, j), 边在抽取的字符串i中以j开始的子串
	//list<EdgeType> info;
	struct EdgeNode* headlink;      //链域，指向下一个终点相同的边
	EdgeNode* taillink;             //链域，指向下一个起点相同的边
	//EdgeNode() {
	//    info.reserve(500);
	//}
}EdgeNode;

typedef struct VertexNode       //顶点表结构
{
	VertexType data;        //顶点域，存储顶点信息
	int visited;            //可访问次数
	EdgeNode* firstin;        //入边表头指针
	int indegree;
	EdgeNode* firstout;        //出边表头指针
	int outdegree;
}VertexNode, AdjList[MAXVEX];

typedef struct
{
	AdjList adjList;
	int numVertexes, numEdges;  //图中当前顶点数和边数
}GraphList;

typedef struct
{
	VertexNode adjList[MAXVEX / TOTALTHREAD];
	int numVertexes, numEdges;
}GraphListThread;

vector<string> subS;			//存取抽取的字符串
unordered_map<string, int> V[TOTALTHREAD + 1];    //顶点
GraphList g[TOTALTHREAD + 1];
int k;

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

//制造字符串
string randstr(const int len)
{
	int i;
	char* str = new char[len + 3];
	for (i = 0; i < len; ++i)
	{
		str[i] = 'A' + rand() % 26;
	}
	str[i] = '\0';
	//string result(str);
	return str;
}

string extractstr(string str, int sublen, int len)
{
	//int index = rand() % (len - sublen + 1);
	int index = (int)((double)rand() / RAND_MAX * len) % (len - sublen + 1);
	string result(str, index, sublen);
	return result;
}

//编辑距离
int cmp_levenshtein(const char* s1, const char* s2)
{
	int row = strlen(s1);               /* s1 的长度 */
	int col = strlen(s2);               /* s2 的长度 */

	int **mat = new int*[row];                  /* C99 - variable-length array */
	for (int i = 0; i < row; i++)
	{
		mat[i] = new int[col];
	}

	for (int i = 0; i < row; ++i) {        /* 数组的行 */
		for (int j = 0; j < col; ++j) {    /* 数组的列 */
			if (i == 0) {
				mat[i][j] = j;          /* 初始化第1行为 [ 0 1 2 ... ] */
			}
			else if (j == 0) {
				mat[i][j] = i;          /* 初始化第1列为 [ 0 1 2 ... ] */
			}
			else {
				int cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1;     /* 记录s1[i-1]与s2[j-1]是否相等 */
				mat[i][j] = MIN3(mat[i - 1][j] + 1,           /* 取三者的最小值 */
					mat[i][j - 1] + 1,
					mat[i - 1][j - 1] + cost);
			}
		}
	}

	return mat[row - 1][col - 1];
}

void* constructThread(void* arg)
{
	int n = (int)arg;             //当前线程标号
	int startindex = subS.size() / TOTALTHREAD * n;
	int endindex = n == TOTALTHREAD - 1 ? subS.size() : startindex + subS.size() / TOTALTHREAD;
	n = n + 1;
	for (int i = startindex; i < endindex; i++) {
		for (int j = 0; j < subS[i].length() - k + 1; j++) {
			string substring(subS[i], j, k);
			string substringL(subS[i], j, k - 1);
			string substringR(subS[i], j + 1, k - 1);
			int Lindex = -1;
			int Rindex = -1;
			//pthread_mutex_lock(&mutex);
			if (j == 0) {
				if (V[n].find(substringL) == V[n].end()) {
					int numofV = V[n].size();
					V[n][substringL] = numofV;                      //新建顶点
					g[n].adjList[numofV].data = substringL;
					g[n].adjList[numofV].firstout = NULL;
					g[n].adjList[numofV].firstin = NULL;
				}
			}
			Lindex = V[n][substringL];
			if (V[n].find(substringR) == V[n].end()) {
				int numofV = V[n].size();
				V[n][substringR] = numofV;                      //新建顶点
				g[n].adjList[numofV].data = substringR;
				g[n].adjList[numofV].firstout = NULL;
				g[n].adjList[numofV].firstin = NULL;
			}
			Rindex = V[n][substringR];

			EdgeNode* findnode = g[n].adjList[Lindex].firstout;
			bool flag = false;
			while (findnode != NULL) {                      //判断是有重复边
				if (findnode->tailvex == Rindex) {
					EdgeType tmp;
					tmp.stringindex = i;
					tmp.startindex = j;
					findnode->info.push_back(tmp);          //存储边在抽取字符串的信息
					flag = true;
					break;
				}
				findnode = findnode->taillink;
			}
			if (!flag) {
				EdgeNode* newE = new EdgeNode;
				//邻接序号为j
				newE->tailvex = Rindex;
				newE->headvex = Lindex;
				//将e指针指向当前顶点指向的结构
				newE->taillink = g[n].adjList[Lindex].firstout;
				newE->headlink = g[n].adjList[Rindex].firstin;
				//存储边在抽取字符串的信息
				EdgeType tmp;
				tmp.stringindex = i;
				tmp.startindex = j;
				newE->info.push_back(tmp);
				//将当前顶点的指针指向e
				g[n].adjList[Lindex].firstout = newE;
				g[n].adjList[Rindex].firstin = newE;
				g[n].adjList[Rindex].visited++;
			}
			//pthread_mutex_unlock(&mutex);
		}
	}
	return nullptr;
}

void constructDebruijn()
{
	pthread_t mythread[TOTALTHREAD];
	//clock_t t;
	//t = clock();
	for (int i = 0; i < TOTALTHREAD; i++)				//创建线程分别处理抽取的子串
	{

		if (pthread_create(&mythread[i], NULL, constructThread, (void*)i) == -1) {
			puts("fail to create pthread ");
			exit(1);
		}
	}
	for (int i = 0; i < TOTALTHREAD; i++)
	{
		if (pthread_join(mythread[i], NULL) == -1) {
			puts("fail to recollect ");
			exit(1);
		}
	}
	//t = clock() - t;

	//printf("time=%lf s\n", ((float)t) / CLOCKS_PER_SEC);

	for (int i = 1; i < TOTALTHREAD + 1; i++)		//综合各线程结果
	{
		auto iter = V[i].begin();
		while (iter != V[i].end())
		{
			if (V[0].find(iter->first) == V[0].end()) {
				int numofV = V[0].size();
				V[0][iter->first] = numofV;                      //新建顶点
				g[0].adjList[numofV].data = iter->first;
				g[0].adjList[numofV].firstout = NULL;
				g[0].adjList[numofV].firstin = NULL;
				g[0].adjList[numofV].indegree = 0;
				g[0].adjList[numofV].outdegree = 0;
			}
			int Lindex = V[0][iter->first];
			int Rindex = -1;
			EdgeNode* partnode = g[i].adjList[iter->second].firstout;
			while (partnode != NULL)
			{
				string cur_Rstr = g[i].adjList[partnode->tailvex].data;
				if (V[0].find(cur_Rstr) == V[0].end()) {             //如果没有尾顶点，则新建顶点
					int numofV = V[0].size();
					V[0][cur_Rstr] = numofV;                      //新建顶点
					g[0].adjList[numofV].data = cur_Rstr;
					g[0].adjList[numofV].firstout = NULL;
					g[0].adjList[numofV].firstin = NULL;
					g[0].adjList[numofV].indegree = 0;
					g[0].adjList[numofV].outdegree = 0;
				}
				Rindex = V[0][cur_Rstr];
				EdgeNode* finalnode = g[0].adjList[Lindex].firstout;
				bool flag = false;
				while (finalnode != NULL)
				{
					if (g[0].adjList[finalnode->tailvex].data == cur_Rstr) {
						finalnode->info.insert(finalnode->info.end(), partnode->info.begin(), partnode->info.end());    //存储边在抽取字符串的信息
						if (g[0].adjList[finalnode->headvex].visited >= 2 &&
							g[0].adjList[finalnode->headvex].outdegree < g[0].adjList[finalnode->headvex].visited)
							g[0].adjList[finalnode->tailvex].visited = g[0].adjList[finalnode->headvex].visited;
						flag = true;
						break;
					}
					finalnode = finalnode->taillink;
				}
				if (!flag) {
					EdgeNode* newE = new EdgeNode;
					//邻接序号
					newE->tailvex = Rindex;
					newE->headvex = Lindex;
					//将指针指向当前顶点指向的结构
					newE->taillink = g[0].adjList[Lindex].firstout;
					newE->headlink = g[0].adjList[Rindex].firstin;
					//存储边在抽取字符串的信息
					newE->info.insert(newE->info.end(), partnode->info.begin(), partnode->info.end());
					//将当前顶点的指针指向newE
					g[0].adjList[Lindex].firstout = newE;
					g[0].adjList[Rindex].firstin = newE;
					g[0].adjList[Rindex].visited++;
					g[0].adjList[Lindex].outdegree++;
					g[0].adjList[Rindex].indegree++;
				}
				partnode = partnode->taillink;
			}
			iter++;
		}
	}
}


//遍历图生成字串S'
void dfs(int index, EdgeNode* lastnode, string& result)
{
	EdgeNode* nextnode = g[0].adjList[index].firstout;
	bool flag = false;
	while (nextnode != NULL && lastnode != NULL)	//寻找下一个适合的访问顶点
	{
		for (auto itlast = lastnode->info.begin(); itlast != lastnode->info.end(); ++itlast)
		{
			for (auto itnext = nextnode->info.begin(); itnext != nextnode->info.end(); ++itnext)
			{
				if (itlast->stringindex == itnext->stringindex &&
					itlast->startindex + 1 == itnext->startindex)
				{
					flag = true;
					break;
				}
			}
			if (flag)
				break;
		}
		if (flag)
			break;
		nextnode = nextnode->taillink;
	}
	while (nextnode != NULL)
	{
		int e = nextnode->tailvex;              //下一个访问顶点的下标
		if (g[0].adjList[e].visited > 0)
		{
			result = result + g[0].adjList[e].data[g[0].adjList[e].data.size() - 1];
			g[0].adjList[e].visited--;
			dfs(e, nextnode, result);
		}
		nextnode = nextnode->taillink;
	}
}

int main()
{
	clock_t t;
	srand(time(NULL));
	t = clock();
	//制造测试集
	string S;
	S = randstr(100000);
	//S = "ABCDAEFCDAGB";
	//S = "ABCDAEFCDAEFGB";
	cout << S << endl;
	cout << "字串集：" << endl;
	for (int i = 0; i < 1000000; i++)				  //制造抽取的子串集
	{
		//int length = 6 + rand() % 5;                //随机抽取长度为6-10的子串
		int length = 60 + rand() % 41;
		string tmp = extractstr(S, length, S.length());
		subS.push_back(tmp);
	}

	//程序开始
	k = 51;
	constructDebruijn();
 	cout << "顶点个数：" << V[0].size() << endl;

	int i = 0;
	int startindex = 0;
	while (g[0].adjList[i].firstin != NULL && i < MAXVEX)
	{
		i++;
	}
	startindex = i;
	string result(g[0].adjList[startindex].data);
	dfs(startindex, NULL, result);
	cout << S << endl;
	cout << result << endl;
	cout << "V最大小：" << V[0].max_size() << endl;
	cout << "V大小：" << V[0].size() << endl;
	cout << "S长度：" << S.length() << "   result长度：" << result.length() << endl;
	//cout << "编辑距离：" << cmp_levenshtein(S.c_str(), result.c_str());
	t = clock() - t;

	printf("time=%lf s\n", ((float)t) / CLOCKS_PER_SEC);
}

